|
In computer programming, particularly functional programming and type theory, an algebraic data type is a kind of composite type, i.e. a type formed by combining other types. Two common classes of algebraic type are product types—i.e. tuples and records—and sum types, also called tagged or disjoint unions or ''variant types''.〔(Records and variants ) - OCaml manual section 1.4 〕 The values of a product type typically contain several values, called ''fields''. All values of that type have the same combination of field types. The set of all possible values of a product type is the set-theoretical product of the sets of all possible values of its field types. The values of a sum type are typically grouped into several classes, called ''variants''. A value of a variant type is usually created with a quasi-functional entity called a ''constructor''. Each variant has its own constructor, which takes a specified number of arguments with specified types. The set of all possible values of a sum type is the set-theoretical sum, i.e. the disjoint union, of the sets of all possible values of its variants. Enumerated types are a special case of sum types in which the constructors take no arguments, as exactly one value is defined for each type. Values of algebraic types are analyzed with pattern matching, which identifies a value by its constructor or field names and extracts the data it contains. Algebraic data types were introduced in Hope, a small functional programming language developed in the 1970s at Edinburgh University. ==Examples== One of the most common examples of an algebraic data type is the singly linked list. A list type is a sum type with two variants, Nil for an empty list and Cons ''x'' ''xs'' for the combination of a new element ''x'' with a list ''xs'' to create a new list:data List a = Nil | Cons a (List a) Cons is an abbreviation of ''cons''truct. Many languages have special syntax for lists. For example, Haskell and ML use 1::2::3::[] or [1;2;3] in ML.For another example, in Haskell we can define a new algebraic data type, Tree:data Tree = Empty | Leaf Int | Node Tree Tree Here, Empty represents an empty tree, Leaf contains a piece of data, and Node organizes the data into branches.In most languages that support algebraic data types, it is possible to define parametric types. Examples are given later in this article. Somewhat similar to a function, a data constructor is applied to arguments of an appropriate type, yielding an instance of the data type to which the type constructor belongs. For instance, the data constructor Leaf is logically a function Int -> Tree, meaning that giving an integer as an argument to Leaf produces a value of the type Tree. As Node takes two arguments of the type Tree itself, the datatype is recursive.Operations on algebraic data types can be defined by using pattern matching to retrieve the arguments. For example, consider a function to find the depth of a Tree, given here in Haskell:depth :: Tree -> Int depth Empty = 0 depth (Leaf n) = 1 depth (Node l r) = 1 + max (depth l) (depth r) Thus, a Tree given to depth can be constructed using any of Empty, Leaf or Node and we must match for any of them respectively to deal with all cases. In case of Node, the pattern extracts the subtrees l and r for further processing.Algebraic data types are particularly well-suited to the implementation of abstract syntax. For instance, the following algebraic data type describes a simple language representing numerical expressions: data Expression = Number Int | Add Expression Expression | Minus Expression | Mult Expression Expression | Divide Expression Expression An element of such a data type would have a form such as Mult (Add (Number 4) (Minus (Number 1))) (Number 2).Writing an evaluation function for this language is a simple exercise; however, more complex transformations also become feasible. For instance, an optimization pass in a compiler might be written as a function taking an abstract expression as input and returning an optimized form. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algebraic data type」の詳細全文を読む スポンサード リンク
|